package middle;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

public class Solution_313 {

    public static void main(String[] args) {
        Solution_313 model = new Solution_313();
        System.out.println(model.nthSuperUglyNumber(12, new int[]{2, 7, 13, 19}));
        System.out.println(model.nthSuperUglyNumber(1, new int[]{2,3,5}));
        System.out.println(model.nthSuperUglyNumber(5, new int[]{2,3,5}));
        System.out.println(model.nthSuperUglyNumber(67, new int[]{2, 997}));
    }

    public int nthSuperUglyNumber(int n, int[] primes) {
        if (n == 1) {
            return 1;
        }
        Set<Long> set = new HashSet<>();
        set.add(1L);
        PriorityQueue<long[]> queue = new PriorityQueue<>(Comparator.comparingLong(a -> a[2]));
        int length = Math.min(primes.length, n - 1);
        for (int i = 0; i < length; i++) {
            queue.add(new long[]{0L, (long)primes[i], (long)primes[i]});
            set.add((long)primes[i]);
        }

        List<Long> list = new ArrayList<>();
        list.add(1L);
        for (int i = 2; i <= n; i++) {
            long[] poll = queue.poll();
            list.add(poll[2]);
            do {
                poll[0]++;
                poll[2] = poll[1] * list.get((int)poll[0]);
            } while (set.contains(poll[2]));
            queue.add(poll);
            set.add(poll[2]);
        }
//        System.out.println(list);
        return list.get(list.size() - 1).intValue();
    }
}
